﻿using System;
using System.Collections.Generic;
using System.Text;

namespace Data_Structures_and_Algorithms.linear_list
{
    public class StaticLinerarTable : ILinearList
    {
        private StaticLinerarNode[] Data;
        /// <summary>
        /// 数据头的游标
        /// </summary>
        private int HeardIndex { get; set; } = 0;
        public int Length { get; private set; } = 0;

        public StaticLinerarTable() {
            this.Data = new StaticLinerarNode[4];
            for (var i = 0; i < Data.Length-1; i++) {
                this.Data[i] = new StaticLinerarNode { Next = i + 1 };
            }
            this.Data[Data.Length - 1] = new StaticLinerarNode { Next = 0 };
        }

        public void Delete(int index)
        {
            if (index > Length) throw new Exception("超出长度");
            if (index == 1) { // 如果是第一个，那么开始游标变成第二个，第一个位置制空，接入备用链表
                int empty = HeardIndex;
                HeardIndex = this.Data[empty].Next;
                this.Data[empty] = new StaticLinerarNode { Next = this.Data[0].Next};
                this.Data[0].Next = empty;
                return;
            }
            int temp = HeardIndex;
            for (var i = 2; i < index; i++) // 找到前一位置的数据
            {
                temp = Data[temp].Next;
            }
            int delete = this.Data[temp].Next;
            this.Data[temp].Next = this.Data[delete].Next; // 前一个数据直接连接删除数据后的数据
            this.Data[delete] = new StaticLinerarNode { Next = this.Data[0].Next};
            this.Data[0].Next = delete;
        }

        public void Display()
        {
            Console.WriteLine($"表头{HeardIndex}---------------------");
            for (var i = 0; i < Data.Length; i++) {
                Console.WriteLine($"{Data[i].Data??' '} |  {Data[i].Next}");
            }
        }

        public int Find(object data)
        {
            int temp = HeardIndex;
            for (var i = 0; i < Length; i++) // 找到位置的数据
            {
                if (data.Equals(this.Data[temp].Data)) return i + 1;
                temp = Data[temp].Next;
            }
            return -1;
        }

        public object FindAt(int index)
        {
            if (index > Length) throw new Exception("超出长度");
            int temp = HeardIndex;
            for (var i = 1; i < index; i++) // 找到位置的数据
            {
                temp = Data[temp].Next;
            }
           return this.Data[temp].Data;
        }

        public void Insert(int index, object data)
        {

            if (index > Length + 1) throw new Exception("超出长度");
            int insert = GetEmpty(); // 新数据的游标
            if (index == 1) // 插入位置是表头
            {
                this.Data[insert] = new StaticLinerarNode { Data = data, Next = HeardIndex };
                HeardIndex = insert;
            }
            else { // 其他位置插入
                int temp = HeardIndex;
                for (var i = 2; i < index; i++) // 找到位置前的数据
                {
                    temp = Data[temp].Next;
                }

                this.Data[insert] = new StaticLinerarNode { Data = data, Next = this.Data[temp].Next }; // 新数据游标指向该原来该数据位置
                this.Data[temp].Next = insert; //位置前的数据游标指向新数据位置
            }

            Length++;
        }

        public void Update(int index, object data)
        {
            if (index > Length) throw new Exception("超出长度");
            int temp = HeardIndex;
            for (var i = 1; i < index; i++) // 找到位置的数据
            {
                temp = Data[temp].Next;
            }
            this.Data[temp].Data = data;
            return;
        }
        private int GetEmpty() {
            var index = this.Data[0].Next;
            if (index > 0)
            {
                this.Data[0].Next = this.Data[index].Next;
            }
            else {
                // 剩余空间不足
                var len = this.Data.Length;
                Array.Resize<StaticLinerarNode>(ref this.Data, len + 3);
                this.Data[0].Next = len;
                for (var i = len;i<this.Data.Length-1;i++) {
                    this.Data[i] = new StaticLinerarNode {Next=i+1 };
                }
                this.Data[this.Data.Length - 1] = new StaticLinerarNode { Next = 0 };
                return GetEmpty();
            }
            return index;
        }
    }
}
